package com.tyrone.leetcode.editor.cn;

import javax.security.auth.login.CredentialNotFoundException;
import java.util.Arrays;

/**
 * @author yelong.xie
 * @date 2024/1/26 22:01
 */
public class PackageProblem01 {

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.maxValue(3, 4, new int[]{4, 2, 3}, new int[]{4, 2, 3}));
    }

    /**
     * 有N件物品和一个容量是 V的背包。每件物品有且只有一件。
     * 第 i 件物品的体积是 v[i] ，价值是 w[i]。
     * 求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
     * 示例 1：
     * 输入: N = 3, V = 4, v = [4,2,3], w = [4,2,3]
     * 输出: 4
     * 解释: 只选第一件物品，可使价值最大。
     * 示例 2：
     * 输入: N = 3, V = 5, v = [4,2,3], w = [4,2,3]
     * 输出: 5
     * 解释: 不选第一件物品，选择第二件和第三件物品，可使价值最大。
     */
    static class Solution {
        /**
         * 这种问题只能穷举 然后判断可不可行，那么我就直接暴力穷举例，对于每一个物品来说都可以选择选或者不选，这样的话就存在解空间树了
         * 直接用dfs {@link  com.tyrone.leetcode.editor.cn.PackageProblem01.Solution#dfs(int, int, int[], int[])}
         *
         * 但是这样暴搜实际上是重复搜索的 这个时候就需要用到 记忆化搜索 用个map来存储一下就可以
         * {@link  com.tyrone.leetcode.editor.cn.PackageProblem01.Solution#memoryDfs(int, int, int[], int[])}
         *
         * 宫水说
         * 任何记忆化搜索都可以转变成动态规划
         *
         *
         * @param N
         * @param V
         * @param v
         * @param w
         * @return
         */
//        public int maxValue(int N, int V, int[] v, int[] w) {
//            return dfs(N-1,V,v,w);
//        }

        /**
         * dfs搜索解空间
         *
         * @param curr  当前只能从0-curr下标处选择物品
         * @param leave 剩余的容量
         * @param b
         * @param w     重量
         * @return 当前只能从0-curr下标处选择物品，剩余容量为leave 最大值
         */
        int dfs(int curr, int leave, int[] b, int[] w) {
            /**
             * base case 从最后一件物品递归到一件，也就是0-0物品之间 对于剩余容量leave来说能不能选的
             */
            if (curr == 0) return leave >= w[0] ? b[0] : 0;

            /**
             * 当前curr下标处的物品不选的最大价值 等于 0～ curr-1 选择商品 并且容量为leave的值
             */
            int currNotSelect = dfs(curr - 1, leave, b, w);

            int currSelect = 0;
            if (leave >= w[curr]) {
                currSelect = dfs(curr - 1, leave - w[curr], b, w) + b[curr];
            }
            /**
             * 当前下标处物品选择的时候的最大价值 = 0～curr-1 选择商品 并且容量为 leave-curr的容量的价值    + curr的价值
             */
            return Math.max(currSelect, currNotSelect);

        }


        /**
         * 记忆化搜索
         *
         * @param N
         * @param V
         * @param v
         * @param w
         * @return
         */

        int[][] cache;


//        public int maxValue(int N, int V, int[] v, int[] w) {
//            cache = new int[N][V+1];
//            for (int i = 0; i < cache.length; i++) {
//                Arrays.fill(cache[i],Integer.MIN_VALUE);
//            }
//            return memoryDfs(N-1,V,v,w);
//        }

        private int memoryDfs(int curr, int leave, int[] v, int[] w) {
            /**
             * 如果有缓存的化直接返回
             */
            if (cache[curr][leave] != Integer.MIN_VALUE) return cache[curr][leave];

            /**
             * base case
             */
            if (curr == 0) return leave >= w[0] ? v[0] : 0;

            /**
             * 当前curr下标处的物品不选的最大价值 等于 0～ curr-1 选择商品 并且容量为leave的值
             */
            int currNotSelect = dfs(curr - 1, leave, v, w);

            int currSelect = 0;
            if (leave >= w[curr]) {
                currSelect = dfs(curr - 1, leave - w[curr], v, w) + v[curr];
            }
            /**
             * 当前下标处物品选择的时候的最大价值 = 0～curr-1 选择商品 并且容量为 leave-curr的容量的价值    + curr的价值
             */
            int max = Math.max(currSelect, currNotSelect);
            cache[curr][leave] = max;
            return max;
        }


        /**
         * 动态规划
         *
         * @param N
         * @param C
         * @param v
         * @param w
         * @return
         */
//        public int maxValue(int N, int C, int[] v, int[] w) {
//            int[][] dp = new int[N][C + 1]; // 表示0-N之间选 或者说枚举到N 并且容量为V的情况下的最大价值
//            for (int i = 0; i < C; i++) {
//                dp[0][i] = i >= v[0] ? w[0] : 0 ;   //表示第一件在不同的容易情况下的最大价值
//            }
//            for (int i = 1; i < N; i++) {
//                for (int j = 0; j < C + 1; j++) {
//                    //不选
//                    int currNotSelect = dp[i - 1][j];
//                    //选
//                    int currSelect = 0;
//                    if (j >= v[i]) {
//                        currSelect = dp[i - 1][j - v[i]] + w[i];
//                    }
//                    dp[i][j] = Math.max(currSelect, currNotSelect);
//                }
//            }
//            return dp[N - 1][C];
//        }


        public int maxValue(int N, int C, int[] v, int[] w) {
            int[] dp = new int[C + 1];
            for (int i = 0; i < N; i++) {
                for (int j = C; j >= v[i]; j--) {
                    // 不选该物品
                    int n = dp[j];
                    // 选择该物品
                    int y = dp[j-v[i]] + w[i];
                    dp[j] = Math.max(n, y);
                }
            }
            return dp[C];
        }

    }
}
